package leetcode.primary;

public class T43 {
    int len1;
    int len2;
    public String multiply(String num1, String num2) {
        if (num1.charAt(0)=='0'||num2.charAt(0)=='0'){
            return String.valueOf(0);
        }
        StringBuilder ans= new StringBuilder();
         len1 = num1.length();
         len2 = num2.length();
        int[][] temp = new int[len2][len1+len2];
        for (int i=len2-1;i>=0;i--){
            int carry = 0;
            int y = num2.charAt(i)-'0';
            for (int j=len1-1;j>=0;j--){
                int x = num1.charAt(j)-'0';
                int product = x*y+carry;
                carry = product/10;
                temp[i][len1-j-1] = product%10;
                System.out.print(product%10);
            }
            temp[i][len1] = carry;
            System.out.println();
        }
        for (int i = len2-2;i>=0;i--){
            int move = len2-i-1;
            Move(temp,move,i);
        }

        for (int i=0;i<len2;i++){
            for (int j =0;j<len1+len2;j++){
                System.out.print(temp[i][j]);
            }
            System.out.println();
        }
        int carry = 0;
        for (int j=0;j<len1+len2;j++){
            int sum =0;
            for (int i=0;i<len2;i++){
                sum+=temp[i][j];
            }
            sum+=carry;
            carry = sum/10;
            char ch = (char) (sum%10+'0');
            ans.append(ch);
        }

        if (ans.charAt(len1+len2-1)=='0'){
            ans.deleteCharAt(len1+len2-1);
        }
        return  ans.reverse().toString();
    }

    public void Move(int[][] temp,int move,int i){
        int j;
        for (j=len1+len2-1;j>=0;j--){
            if (temp[i][j]!=0){
                break;
            }
        }
        for (int k=j;k>=0;k--){
            temp[i][k+move] = temp[i][k];
            temp[i][k] = 0;
        }

    }

    public static void main(String[] args) {
        T43 test = new T43();
        String ans = test.multiply("123","456");
        System.out.println(ans);
    }
}
